﻿#pragma once

//头文件
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>


#define MaxINt 32767		//表示权值的最大值
#define MVNum 100			//最大顶点数


typedef char VerTexType;	//假设定点的数据类型为字符型
typedef int ArcType;		//假设边的权值类型为整型

//图类型
typedef struct
{
	VerTexType vexs[MVNum];			//顶点表
	ArcType arcs[MVNum][MVNum];		//邻接矩阵
	int vexnum;						//图当前的点数
	int arcnum;						//图当前的边数
}AMGraph;

//辅助数组
//结构体数组Edge:存储边的信息，包括边的两个顶点信息和权值
typedef struct
{
	VerTexType Head;		//边的始点
	VerTexType Tail;		//边的终点
	ArcType lowcost;		//边上的权值
}Auxiliary;

//Vexset[i]
//标识各个顶点所在的连通分量
//初始时Vexset[i]=i，表示各顶点自成一个连通分量
//细节：
// 1.Vexset数组的下标，对应的是顶点表中各个顶点的下标
// 2.初始时有vexnum个连通分量，它们后来会合并


//邻接矩阵的创建
void CreateDUN(AMGraph* G);

//确定点在图中的位置
int LocateVex(AMGraph* G, VerTexType x);

//打印邻接矩阵
void PrintArc(AMGraph* G);

//克鲁斯卡尔算法
MiniSpanTree_Kruskal(AMGraph* G);

//创建辅助数组Edge
Auxiliary* Creat_Edge(AMGraph* G);

//创建辅助数组Vexset
int* Creat_Vexset(AMGraph* G);